import java.util.HashMap;

/**
* @description: 460. LFU 缓存
* @author hewei
* @date 2022/8/9 15:02
* @version 1.0
*/

public class LFUCache {

    int capacity;
    HashMap<Integer, Node> map;
    HashMap<Integer, DoubleLinkedList> frqMap;
    int minFrq;
    public LFUCache(int capacity) {
        this.minFrq = Integer.MAX_VALUE;
        this.capacity = capacity;
        map = new HashMap<>();
        frqMap = new HashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        update(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            update(node);
            node.value = value;
        } else {
            if (capacity == map.size()) {
                if (capacity == 0) return;
                map.remove(frqMap.get(minFrq).del());
                if (frqMap.get(minFrq).isEmpty()) {
                    frqMap.remove(minFrq);
                }
            }
            Node node = new Node(1, value, key);
            if (!frqMap.containsKey(1)) frqMap.put(1, new DoubleLinkedList());
            frqMap.get(1).add(node);
            map.put(key, node);
            minFrq = 1;
        }
    }

    public void update(Node node) {
        int frq = node.frq;
        frqMap.get(frq).remove(node);
        if (frqMap.get(frq).isEmpty() && frq == minFrq) {
            frqMap.remove(node.frq);
            minFrq++;
        }
        if (!frqMap.containsKey(frq + 1)) frqMap.put(frq + 1, new DoubleLinkedList());
        node.frq = frq + 1;
        frqMap.get(frq + 1).add(node);
    }

    static class Node {
        int frq;
        int value;
        int key;
        Node left, right;

        public Node(int frq, int value, int key) {
            this.frq = frq;
            this.value = value;
            this.key = key;
        }

        public Node() {
        }
    }

    static class DoubleLinkedList {
        Node dummyHead;
        Node dummyTail;

        public DoubleLinkedList() {
            dummyHead = new Node();
            dummyTail = new Node();
            dummyTail.left = dummyHead;
            dummyHead.right = dummyTail;
        }

        public void remove(Node node) {
            node.left.right = node.right;
            node.right.left = node.left;
        }

        public void add(Node node) {
            node.left = dummyHead;
            node.right = dummyHead.right;
            dummyHead.right.left = node;
            dummyHead.right = node;
        }

        public boolean isEmpty() {
            return dummyHead.right == dummyTail;
        }

        public int del() {
            int res = dummyTail.left.key;
            dummyTail.left = dummyTail.left.left;
            dummyTail.left.right = dummyTail;
            return res;
        }
    }
}
